package LeetCode.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 括号生成
 * @author: leiwenkang02@meituan.com
 * @date: 2018/9/25
 * @time: 20:26
 */
public class Test22括号生成 {
    public static void main(String[] args) {
        List<String> list = generateParenthesis(3);
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i));
            System.out.println();
        }

    }
    public static List<String> generateParenthesis(int n) {
         List<String> list = new ArrayList<>();
         backTrack(list, "", 0, 0, n);
         return list;
    }

    //每次选一个括号，有两种可能
    // 如果该位置选的左括号，则递归其他剩余位置所有的可能情况
    // 同样如果该位置选的右括号，则递归其他剩余位置所有的可能情况

    /**
     * 举例说明，n=3的情况，第一个位置已经选了（，现在第一个位置已经选了（，对于第二个位置就有两个选择
     * 1.选择左括号，则str为((，则递归余下所有可能情况
     * 2.选择右括号，则str为()，则递归余下所有可能情况
     * 类似高中数学学的排列组合，3个红球，3个篮球，放入N个不同的框子里，有多少种顺序，只是这里加了约束条件，每次左括号必须大于右括号数。
     * 每个框子有两种可能，每次选择一种球放入框子
     */


    public static void backTrack(List<String> list, String str, int open, int close, int n) {
        if (str.length() == 2 * n) {
            list.add(str);
            return;
        }
        if (open < n) {
            backTrack(list, str + "(", open + 1, close, n);
        }
        if (close < open) {
            backTrack(list, str + ")", open, close + 1, n);
        }
    }
}
